using Xunit;
using Newtonsoft.Json;
using System.Collections.Generic;
using System.Reflection;
using System;

namespace LeetCodeQuestionBank.Algorithm
{
    public class No0852_PeakIndexInMountainArray
    {
        /*
        符合下列属性的数组 arr 称为 山脉数组 ：
            arr.length >= 3
            存在 i（0 < i < arr.length - 1）使得：
                arr[0] < arr[1] < ... arr[i-1] < arr[i]
                arr[i] > arr[i+1] > ... > arr[arr.length - 1]
        给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

        示例 1：
            输入：arr = [0,1,0]
            输出：1
        示例 2：
            输入：arr = [0,2,1,0]
            输出：1
        示例 3：
            输入：arr = [0,10,5,2]
            输出：1
        示例 4：
            输入：arr = [3,4,5,1]
            输出：2
        示例 5：
            输入：arr = [24,69,100,99,79,78,67,36,26,19]
            输出：2
        提示：
            3 <= arr.length <= 104
            0 <= arr[i] <= 106
            题目数据保证 arr 是一个山脉数组
        进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
        */

        public static IEnumerable<object[]> GetTestArgs()
        {
            return new object[][] {
                new object[] { new int[] { 0,1,0 }, 1 },
                new object[] { new int[] { 0,2,1,0 }, 1 },
                new object[] { new int[] { 0,10,5,2 }, 1 },
                new object[] { new int[] { 3,4,5,1 }, 2 },
                new object[] { new int[] { 24,69,100,99,79,78,67,36,26,19 }, 2 },
            }.MergeFuncNames(new string[] {
                nameof(PeakIndexInMountainArray),
                nameof(PeakIndexInMountainArray_BinarySearch),
            });
        }

        [Theory]
        [MemberData(nameof(GetTestArgs))]
        public void OnExecute(string funcName, int[] input, int answer)
        {
            Type type = this.GetType();
            MethodInfo methodInfo = type.GetMethod(funcName);
            int output = (int)methodInfo.Invoke(this, new object[] { input });
            Assert.Equal(answer, output);
        }

        public int PeakIndexInMountainArray(int[] arr)
        {
            for (int i = 1; i < arr.Length - 1; i++)
            {
                if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1])
                {
                    return i;
                }
            }
            return 0;
        }
        public int PeakIndexInMountainArray_BinarySearch(int[] arr)
        {
            int n = arr.Length;
            int left = 1, right = n - 2, ans = 0;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (arr[mid] > arr[mid + 1])
                {
                    ans = mid;
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return ans;
        }
    }
}
